1. Field of the Invention
The present invention relates to an apparatus and method for displaying images on a video display. Specifically, the present invention relates to an apparatus and method for generating visually improved images on a video display where the image is generated at least in part from a collection of triangular graphics primitives.
2. Prior Art
Many computer systems today are capable of displaying complex 3-dimensional curves and solids display devices which are controlled by these computer systems. For example, complex 3-dimensional solids and curves may be displayed on video displays which are controlled by computer systems, and these computer systems often allow the user of the system to manipulate (e.g., rotate, scale, etc.) the object which is displayed. These computer systems often use well known graphics techniques for redering these 3-D curves and solids, such as hidden surface algorithms (sometimes referred to as Z buffering) and Gouraud shading as well as other classic computer graphics techniques such as clipping the displayed object so that it appears through a window. See, e.g., Newman and Sproull, Principles of Interactive Computer Graphics, 2nd Edition, McGraw-Hill, 1979; and Foley and Van Dam, Fundamentals of Interactive Computer Graphics, Addision-Wesley, 1982.
These various graphics techniques may be implemented on general purpose computers as well as computers that have specialized graphics engines which are typically hardware/software combinations designed to handle and manipulate image data which is used to render objects for viewing. These specialized graphics engines typically attempt to reduce a complex 3-D curve or solid to a certain type of polygon (often referred to as a fundamental graphic primitive) which the system is designed to manipulate. General purpose computers that have no specialized graphics engines will typically have commercially available software which can render 3-D curves and solids on a general purpose computer machine, and this software often will attempt to break down complex 3-D curves and solids into smaller polygons of a certain variety (i.e., a graphic primitive) in order to render these complex objects to thereby display them. As is well known in the art, these graphics primitives attempt to approximate the complex 3-dimensional surface which the computer user seeks to display. Typically, a plurality of graphics primitives is used to portray the object, although these primitives usually only approximate the surface. See, for example, Foley and Van Dam, supra, page 582 (picture of a Volkswagen Beetle).
Often, these computer systems utilize triangles as the fundamental area primitive, and accordingly complex 3-dimensional curves and solids are typically broken down into a plurality of triangles which are then processed further using well known graphics techniques (e.g., hidden surface algorithm, clipping, filling polygons, Gouraud shading, projection to the coordinate system of the viewer, etc.) to complete the generation of the image on a display device which is controlled by the computer system. The plurality of triangles approximates the complex surface. In these systems which utilize the triangle as the fundamental area primitive, there is often a need to decompose a quadrilateral into two (or more) triangles.
In the past, quadrilaterals have been decomposed by either connecting vertices 0 and 2 (which are a pair of opposing vertices in the quadrilateral) or vertices 1 and 3 (which is the other pair of opposing vertices of the quadrilateral) to thereby form two triangles. That is, the system is designed to always select one pair of opposing vertices. Alternatively, one may randomly pick one of the two pairs of opposing vertices and connect those vertices to form two triangles within the quadrilateral.
These prior art techniques for decomposing the quadrilateral do not consistently yield good results which are visually pleasing to the viewer. For example, if the selection of opposing vertices is incorrectly made, shading quality suffers substantially as compared to a computer system which simply renders the quadrilateral with Gouraud shading with no decomposition of that quadrilateral into triangles. Of course, if the selection fortuitously is made correctly, shading of surfaces will be substantially improved over computer systems which do not attempt to decompose the quadrilateral into triangles.
It is an object of this invention to provide an improve method and apparatus for producing a visually improved image by consistently decomposing quadrilaterals to a pair of triangles so that the resulting image is visually improved over the prior art techniques.